#include <stdio.h>

// 直接插入排序，升序（从小到大）
void insert_sort(int A[], int n) {
    // 从第2个记录开始，查找其在有序的前半部分的位置
    for (int i = 1; i < n; ++i) {
        // 存留比较基准,第i个待排记录
        // 之所以存留，因一旦不断前行比较，其位置要被占
        int tmp = A[i]; 
        int j;   // 声明在循环体外面，因循环后还要用
        // 对前半有序部分（处于该记录的前面），从后往前，逐个对比
        // 如果前面某记录(第j位)比待插记录(第i个)小，不用再往前了，否则继续往前
        // 继续往前，往前的动作，其实就是其所处位置之后记录的后移
        for (j = i - 1; j >= 0 && tmp < A[j]; --j)
        {
            // 后移过程由j控制
            A[j + 1] = A[j];
        }
        // 待排记录，再移动时，其位被占（尚无处安放）
        // 直至找到合适位置，才重新进入记录。
        A[j + 1] = tmp;
    }
}

void traverse(int A[], int n) {
    for (int i = 0; i < n; ++ i) {
        printf("%d ", A[i]);
    }
    printf("\n");
}

int main()
{
    int A[] = {3,5,27,10,20,17,4,23,2,11};
    int n = sizeof(A) / sizeof(int);
    printf("array length: %d \n", n);
    insert_sort(A, n);
    traverse(A, n);
}